class Solution(object):
    def isEvenOddTree(self, root):
        index = 0
        st = [root]
        while st:
            val = []
            next_st = []
            for node in st:
                if index % 2:
                    if node.val % 2:
                        return False
                else:
                    if not node.val % 2:
                        return False
                if not val:
                    val.append(node.val)
                else:
                    if index % 2:
                        if node.val >= val[-1]:
                            return False
                    else:
                        if node.val <= val[-1]:
                            return False
                    val.append(node.val)
                if node.left:
                    next_st.append(node.left)
                if node.right:
                    next_st.append(node.right)
            st = next_st
            index += 1
        return True
